home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / rex.lha / rex / m2c / Nfa.c < prev    next >
C/C++ Source or Header  |  1992-08-18  |  7KB  |  340 lines
  1. #include "SYSTEM_.h"
  2.  
  3. #ifndef DEFINITION_DynArray
  4. #include "DynArray.h"
  5. #endif
  6.  
  7. #ifndef DEFINITION_IO
  8. #include "IO.h"
  9. #endif
  10.  
  11. #ifndef DEFINITION_Layout
  12. #include "Layout.h"
  13. #endif
  14.  
  15. #ifndef DEFINITION_ScanTabs
  16. #include "ScanTabs.h"
  17. #endif
  18.  
  19. #ifndef DEFINITION_GenTabs
  20. #include "GenTabs.h"
  21. #endif
  22.  
  23. #ifndef DEFINITION_Nfa
  24. #include "Nfa.h"
  25. #endif
  26.  
  27. Nfa_NStateRange Nfa_NStateCount;
  28. Nfa_TransitionRange Nfa_TransitionCount;
  29.  
  30. #define InitialTransitionTableSize    4096
  31. typedef struct S_1 {
  32.     CHAR Ch;
  33.     Nfa_NStateRange NextState;
  34.     Nfa_TransitionRange NextTrans;
  35. } C_1_Transition;
  36. typedef struct S_2 {
  37.     Nfa_TransitionRange Transitions;
  38.     ScanTabs_RuleType Semantics;
  39. } NStateInfo;
  40. typedef struct S_3 {
  41.     NStateInfo A[100000 + 1];
  42. } NStateTable;
  43. typedef struct S_4 {
  44.     C_1_Transition A[100000 + 1];
  45. } TransitionTable;
  46. static NStateTable *NStateTablePtr;
  47. static LONGINT NStateTableSize;
  48. static TransitionTable *TransitionTablePtr;
  49. static LONGINT TransitionTableSize;
  50. static void WriteTransitions ARGS((Nfa_TransitionRange Transition));
  51.  
  52.  
  53. Nfa_NStateRange Nfa_MakeNState
  54. # ifdef __STDC__
  55. (Nfa_TransitionRange pTransitions)
  56. # else
  57. (pTransitions)
  58. Nfa_TransitionRange pTransitions;
  59. # endif
  60. {
  61.   INC(Nfa_NStateCount);
  62.   if (Nfa_NStateCount == NStateTableSize) {
  63.     DynArray_ExtendArray((ADDRESS *)&NStateTablePtr, &NStateTableSize, (LONGINT)sizeof(NStateInfo));
  64.   }
  65.   {
  66.     register NStateInfo *W_1 = &NStateTablePtr->A[Nfa_NStateCount];
  67.  
  68.     W_1->Transitions = pTransitions;
  69.     W_1->Semantics = ScanTabs_NoRule;
  70.   }
  71.   return Nfa_NStateCount;
  72. }
  73.  
  74. void Nfa_PutNSemantics
  75. # ifdef __STDC__
  76. (Nfa_NStateRange State, ScanTabs_RuleType pSemantics)
  77. # else
  78. (State, pSemantics)
  79. Nfa_NStateRange State;
  80. ScanTabs_RuleType pSemantics;
  81. # endif
  82. {
  83.   NStateTablePtr->A[State].Semantics = pSemantics;
  84. }
  85.  
  86. ScanTabs_RuleType Nfa_GetNSemantics
  87. # ifdef __STDC__
  88. (Nfa_NStateRange State)
  89. # else
  90. (State)
  91. Nfa_NStateRange State;
  92. # endif
  93. {
  94.   return NStateTablePtr->A[State].Semantics;
  95. }
  96.  
  97. void Nfa_PutTransitions
  98. # ifdef __STDC__
  99. (Nfa_NStateRange State, Nfa_TransitionRange Transitions)
  100. # else
  101. (State, Transitions)
  102. Nfa_NStateRange State;
  103. Nfa_TransitionRange Transitions;
  104. # endif
  105. {
  106.   NStateTablePtr->A[State].Transitions = Transitions;
  107. }
  108.  
  109. Nfa_TransitionRange Nfa_GetTransitions
  110. # ifdef __STDC__
  111. (Nfa_NStateRange State)
  112. # else
  113. (State)
  114. Nfa_NStateRange State;
  115. # endif
  116. {
  117.   return NStateTablePtr->A[State].Transitions;
  118. }
  119.  
  120. BOOLEAN Nfa_IsLastTransition
  121. # ifdef __STDC__
  122. (Nfa_TransitionRange Transition)
  123. # else
  124. (Transition)
  125. Nfa_TransitionRange Transition;
  126. # endif
  127. {
  128.   return Transition == Nfa_NoTransition;
  129. }
  130.  
  131. Nfa_TransitionRange Nfa_NextTransition
  132. # ifdef __STDC__
  133. (Nfa_TransitionRange Transition)
  134. # else
  135. (Transition)
  136. Nfa_TransitionRange Transition;
  137. # endif
  138. {
  139.   return TransitionTablePtr->A[Transition].NextTrans;
  140. }
  141.  
  142. Nfa_TransitionRange Nfa_MakeTransition
  143. # ifdef __STDC__
  144. (CHAR pCh, Nfa_NStateRange State)
  145. # else
  146. (pCh, State)
  147. CHAR pCh;
  148. Nfa_NStateRange State;
  149. # endif
  150. {
  151.   INC(Nfa_TransitionCount);
  152.   if (Nfa_TransitionCount == TransitionTableSize) {
  153.     DynArray_ExtendArray((ADDRESS *)&TransitionTablePtr, &TransitionTableSize, (LONGINT)sizeof(C_1_Transition));
  154.   }
  155.   {
  156.     register C_1_Transition *W_2 = &TransitionTablePtr->A[Nfa_TransitionCount];
  157.  
  158.     W_2->Ch = pCh;
  159.     W_2->NextState = State;
  160.     W_2->NextTrans = Nfa_NoTransition;
  161.   }
  162.   return Nfa_TransitionCount;
  163. }
  164.  
  165. Nfa_TransitionRange Nfa_AddTransition
  166. # ifdef __STDC__
  167. (Nfa_TransitionRange Transition, Nfa_TransitionRange Transitions)
  168. # else
  169. (Transition, Transitions)
  170. Nfa_TransitionRange Transition, Transitions;
  171. # endif
  172. {
  173.   TransitionTablePtr->A[Transition].NextTrans = Transitions;
  174.   return Transition;
  175. }
  176.  
  177. CHAR Nfa_GetCh
  178. # ifdef __STDC__
  179. (Nfa_TransitionRange Transition)
  180. # else
  181. (Transition)
  182. Nfa_TransitionRange Transition;
  183. # endif
  184. {
  185.   return TransitionTablePtr->A[Transition].Ch;
  186. }
  187.  
  188. Nfa_NStateRange Nfa_GetNextState
  189. # ifdef __STDC__
  190. (Nfa_TransitionRange Transition)
  191. # else
  192. (Transition)
  193. Nfa_TransitionRange Transition;
  194. # endif
  195. {
  196.   return TransitionTablePtr->A[Transition].NextState;
  197. }
  198.  
  199. Nfa_TransitionRange Nfa_UniteTransitions
  200. # ifdef __STDC__
  201. (Nfa_TransitionRange t1, Nfa_TransitionRange t2)
  202. # else
  203. (t1, t2)
  204. Nfa_TransitionRange t1, t2;
  205. # endif
  206. {
  207.   Nfa_TransitionRange t;
  208.  
  209.   if (t1 == Nfa_NoTransition) {
  210.     return t2;
  211.   }
  212.   while (t2 != Nfa_NoTransition) {
  213.     t = TransitionTablePtr->A[t2].NextTrans;
  214.     t1 = Nfa_AddTransition(t2, t1);
  215.     t2 = t;
  216.   }
  217.   return t1;
  218. }
  219.  
  220. Nfa_TransitionRange Nfa_CopyTransitions
  221. # ifdef __STDC__
  222. (Nfa_TransitionRange t1)
  223. # else
  224. (t1)
  225. Nfa_TransitionRange t1;
  226. # endif
  227. {
  228.   Nfa_TransitionRange t2;
  229.  
  230.   t2 = Nfa_NoTransition;
  231.   while (t1 != Nfa_NoTransition) {
  232.     {
  233.       register C_1_Transition *W_3 = &TransitionTablePtr->A[t1];
  234.  
  235.       t2 = Nfa_AddTransition(Nfa_MakeTransition(W_3->Ch, W_3->NextState), t2);
  236.       t1 = W_3->NextTrans;
  237.     }
  238.   }
  239.   return t2;
  240. }
  241.  
  242. void Nfa_WriteNfa
  243. # ifdef __STDC__
  244. ()
  245. # else
  246. ()
  247. # endif
  248. {
  249.   Nfa_NStateRange State;
  250.  
  251.   IO_WriteS((System_tFile)IO_StdOutput, (STRING)"NFA :", 5L);
  252.   IO_WriteNl((System_tFile)IO_StdOutput);
  253.   IO_WriteNl((System_tFile)IO_StdOutput);
  254.   {
  255.     LONGINT B_1 = 1, B_2 = Nfa_NStateCount;
  256.  
  257.     if (B_1 <= B_2)
  258.       for (State = B_1;; State += 1) {
  259.         IO_WriteS((System_tFile)IO_StdOutput, (STRING)"State, Semantics =", 18L);
  260.         IO_WriteI((System_tFile)IO_StdOutput, State, 5L);
  261.         IO_WriteI((System_tFile)IO_StdOutput, (LONGINT)Nfa_GetNSemantics(State), 5L);
  262.         IO_WriteNl((System_tFile)IO_StdOutput);
  263.         WriteTransitions(Nfa_GetTransitions(State));
  264.         IO_WriteNl((System_tFile)IO_StdOutput);
  265.         IO_WriteNl((System_tFile)IO_StdOutput);
  266.         if (State >= B_2) break;
  267.       }
  268.   }
  269.   IO_WriteNl((System_tFile)IO_StdOutput);
  270. }
  271.  
  272. static void WriteTransitions
  273. # ifdef __STDC__
  274. (Nfa_TransitionRange Transition)
  275. # else
  276. (Transition)
  277. Nfa_TransitionRange Transition;
  278. # endif
  279. {
  280.   INTEGER Count;
  281.  
  282.   Count = 0;
  283.   while (!Nfa_IsLastTransition(Transition)) {
  284.     if (Count == 10) {
  285.       IO_WriteNl((System_tFile)IO_StdOutput);
  286.       Count = 0;
  287.     }
  288.     INC(Count);
  289.     Layout_WriteChar((System_tFile)IO_StdOutput, Nfa_GetCh(Transition));
  290.     Layout_WriteSpace((System_tFile)IO_StdOutput);
  291.     IO_WriteI((System_tFile)IO_StdOutput, Nfa_GetNextState(Transition), 1L);
  292.     IO_WriteC((System_tFile)IO_StdOutput, ',');
  293.     Layout_WriteSpace((System_tFile)IO_StdOutput);
  294.     Transition = Nfa_NextTransition(Transition);
  295.   }
  296. }
  297.  
  298. void Nfa_FinalizeNfa
  299. # ifdef __STDC__
  300. ()
  301. # else
  302. ()
  303. # endif
  304. {
  305.   DynArray_ReleaseArray((ADDRESS *)&NStateTablePtr, &NStateTableSize, (LONGINT)sizeof(NStateInfo));
  306.   DynArray_ReleaseArray((ADDRESS *)&TransitionTablePtr, &TransitionTableSize, (LONGINT)sizeof(C_1_Transition));
  307. }
  308.  
  309. void Nfa_BeginNfa
  310. # ifdef __STDC__
  311. ()
  312. # else
  313. ()
  314. # endif
  315. {
  316.   NStateTableSize = GenTabs_LeafCount + 1;
  317.   DynArray_MakeArray((ADDRESS *)&NStateTablePtr, &NStateTableSize, (LONGINT)sizeof(NStateInfo));
  318.   Nfa_NStateCount = 0;
  319.   TransitionTableSize = InitialTransitionTableSize;
  320.   DynArray_MakeArray((ADDRESS *)&TransitionTablePtr, &TransitionTableSize, (LONGINT)sizeof(C_1_Transition));
  321.   Nfa_TransitionCount = 0;
  322. }
  323.  
  324. void BEGIN_Nfa()
  325. {
  326.   static BOOLEAN has_been_called = FALSE;
  327.  
  328.   if (!has_been_called) {
  329.     has_been_called = TRUE;
  330.  
  331.     BEGIN_ScanTabs();
  332.     BEGIN_DynArray();
  333.     BEGIN_IO();
  334.     BEGIN_Layout();
  335.     BEGIN_ScanTabs();
  336.     BEGIN_GenTabs();
  337.  
  338.   }
  339. }
  340.